#include "LinkedList.h"
#include <iostream>
#include <cstdlib>

template <typename T>  
LinkedList<T>::LinkedList(Node<T>* _head)  //初始化函数
{
  head = _head;
};

template <typename T>
LinkedList<T>::~LinkedList()  //析构函数
{
};

template <typename T>
void LinkedList<T>::append(const Node<T>& _node)  //在链表末尾增加一个Node类元素
{
  Node<T>* tail = head;
  Node<T>* p = new Node<T>;
  p->set_data(_node.get_data());
  p->set_next(NULL);
  if (tail != NULL)
    {
      while(tail.get_next() != NULL)
	tail = tail.get_next();
      tail->set_next(p);
    }
  else
    head = p;
};

template <typename T>
void LinkedList<T>::append(T _val)  //在链表末尾增加一个data值为_val的Node类元素
{
   Node<T>* tail = head;
   Node<T>* p = new Node<T>;
   p->set_data(_val);
   p->set_next(NULL);
   if (tail != NULL)
     {
       while(tail.get_next() != NULL)
	 tail = tail.get_next();
       tail->set_next(p);
     }
   else
     head = p;
};

template <typename T>
void LinkedList<T>::list() const  //按顺序输出链表中所有元素的值
{
  Node<T>* pointer = head;
  std::cout << "Linked List: [";
  if (head != NULL)
    {
      while(pointer != NULL)
	{
	  std::cout << pointer->get_data() << " ,";
	  pointer = pointer.get_next();
	}
      std::cout << "/b/b" << "]" << std::endl;
    }
  else  //空列表
    std::cout << "It is an empty list." << std::endl;
};

template <typename T>
T LinkedList<T>::pop_front()  //删除链表第一个元素并返回第一个元素的值
{
  if (head == NULL)  //空列表
    {
      std::cout << "Error! Can not pop a data from an empty list." << std::endl;
      return -1;
    }
  Node<T>* p = head;
  Node<T> data = p->get_data();
  head = p->get_next();
  delete p;
  return data;
};

template <typename T>
Node<T>* LinkedList<T>::find(T _val) const   //返回值为_val的节点的前一个节点的地址，如果没有就返回NULL
{
  Node<T>* p = head;
  if (head == NULL)  //空链表
    {
      std::cout << "It is an empty list." << std::endl;
      return NULL;
    }
  else if (head->get_data() == _val) //第一个节点就是目标节点，无前一个节点，返回NULL
    {
      std::cout << "The first element is the target." << std::endl;
      return NULL;
    }
  else if (head->get_next() == NULL)  //链表只有一个元素，无前一个节点，返回NULL
    {
      std::cout << "There is only one element in this list." << std::endl;
      return NULL;
    }
  else
    {
      Node<T>* last = p;  //last缓存p前一个节点的地址
      p = p->get_next();  //第一个一定不是目标节点，指向第二个元素
      if(p->get_next() != NULL)
	{
	   while(p->get_next() != NULL)
	     {
	       if(p->get_data() == _val)
		 {
		   return last;
		 }
	       else
		 {
		   last = p;
		   p = p->get_next();
		 }
	     }
	}
      else
	{
	  if(p->get_data() == _val)
	    return last;
	  else
	    return NULL;
	}
      return NULL;
    } 
};

template <typename T>
void LinkedList<T>::del(Node<T>* _add)  //删除地址为_add的节点的下一个位置的节点
{
  Node<T>* p = head;
  if (head == NULL) //空链表，不改动
    {
      std::cout << "It is an empty list." << std::endl;
    }
  else if (head->get_next() == NULL) //只有一个元素的列表，不改动
    {
      std::cout << "There is only one element in this list." << std::endl;
    }
  else
    {
      while(p != _add && p->get_next() != NULL)
	p = p->get_next();
      if(p == _add)
	{
	  if (p->get_next() == NULL) //目标节点为最后一个元素，不改动
	    std::cout << "It is the last element in this list." << std::endl;
	  else
	    {
	      Node<T>* q = p->get_next();
	      p->set_next(q->get_next());
	      delete q;
	    }
	}
      else //该链表里没有地址为_add的节点
	std::cout << "Error! There is no such element in this list."
		  << std::endl;
    }
};

template <typename T>
void LinkedList<T>::insert(T _val)  //在链表中插入节点存放_val值，并且保证稳定有序。这里采用升序排列。
{
  Node<T>* a = new Node<T>;
  a->set_data(_val);
  Node<T>* p = head;
  if (head == NULL)  //空链表，直接赋值
    {
      head->set_data(_val);
      head->set_next(NULL);
    }
  else if (head->get_next() == NULL)  //只有一个节点的链表，简单判断
    {
      if (head->get_data() <= _val)
	{
	  a->set_next(NULL);
	  head->set_next(a);
	}
      else
	{
	  a->set_next(head);
	  head = a;
	}
    }
  else
    {
      Node<T>* last = head;
      while (p->get_data() <= _val && p->get_next() != NULL)
	{
	  last = p;
	  p = p->get_next();
	}
      if (p->get_data() <= _val)
	{
	  p->set_next(a);
	  a->set_next(NULL);
	}
      else
	{
	  last->set_next(a);
	  a->set->next(p);
	}
    }
};
